/**
 * @file review.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2022-03-04
 *
 * @copyright Copyright (c) 2022
 *
 */

/** 回溯问题：回溯的本质是穷举
 * 1. 组合 N个数按一定规则找出K个数的集合
 *      需要startIdx调整可选择的范围，已经用过的数不在考虑
 *      77.组合：给定n和k，找出[1,n]中所有可能的k个数组合
 *      216.组合总和III：[1,9]中所有可能相加和为n的k个数组合
 *      17.电话号码的字母组合：难点在于回溯时的变量（数字的索引位置index）
 *      39.组合总和：从数组中找出若干个数使其和为target，数组无重复元素，每个元素无限次选取
 *      40.组合总和II：和上题的区别是数组有重复元素 且 每个数只能用一次
 *          解决：sort先让数组重复元素挨着，然后比较相邻元素即可跳过重复元素
 *          if (i > startIdx && array[i] == array[i - 1]) continue;
 *
 * 2. 分割 某字符串按一定规则的切割方式
 *      131.分割回文串：把某字符串切割成一系列子串，使每个子串都是回文串
 *          要点：切割位置startIdx
 *      93.复原IP地址：将字符串分割成所有合法的点分十进制ip地址
 *          要点：递归出口：点分数量pointNum==3时，判断第四部分是否合法；判断是否合法也是难点
 *
 * 3. 子集 N个数的集合里符合条件的子集
 *      78.子集：数组无重复，求所有子集 -- 此题有迭代解法，比较巧妙
 *          收集所有树节点，而非仅仅叶子结点
 *      90.子集II：数组有重复，子集不能重复
 *          解决：和40.组合总和II一样，sort排序让重复元素紧挨着，然后比较相邻元素即可跳过重复元素
 *          if (i > startIdx && array[i] == array[i - 1]) continue;
 *      491.递增子序列：数组有重复，返回所有递增子序列（长度>=2且无重复）
 *          解决：要去重，但不能排序。首先nums[i] < path.back()构不成递增序列肯定要跳过
 *              其次，通过把nums[i]哈希到used数组上去重（利用nums范围[-100,100]）
 *
 * 4. 排列 N个数按一定规则的全排列
 *      46.全排列：数组无重复元素，求全排列
 *          要点：排列是有序等长的，无需startIdx参数，但需要used数组标记当前已取元素
 *      47.全排列II：数组有重复元素，排列要求不重复
 *          要点：还是老套路，先排序再去重，但又有一些不同
 *          if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
 *          used[i - 1] = false 代表同一树层上前一个元素已取用
 *
 * 5. 棋盘 N皇后 解数独
 *      51.N皇后：N*N的棋盘上摆N个皇后，这些皇后不能同行、不能同列、不能同斜线（45°，135°）
 *          要点：isValid无需检查行（回溯决定行是安全的），剪枝只需检查到当前行
 *      37.解数独：
 *          要点：数独有且仅有一个解，因此回溯函数需要布尔返回值（无解时回溯，找到解就结束了）
 *              isValid检查三个规则（不能出现相同元素）
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution1
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combine(int n, int k)
    {
        backtracking(n, k, 1);
        return res;
    }

    void backtracking(int n, int k, int startIdx)
    {
        // 出口：取满k个数了
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        for (int i = startIdx; i <= n; ++i) {
            // 剪枝：剩余数字不足k个
            if (n - i + 1 < k - path.size()) {
                continue;
            }
            path.push_back(i);
            backtracking(n, k, i + 1);
            path.pop_back();
        }
    }
};

void test77()
{
    Solution1 solve = Solution1();
    vector<vector<int>> nums = solve.combine(4, 2);
    for (auto &num : nums) {
        print(num);
    }
}

class Solution2
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n)
    {
        backtracking(k, n, 1, 0);
        return res;
    }
    void backtracking(int k, int n, int startIdx, int sum)
    {
        // 出口：和大于n 或 达到k个数的限制了
        if (sum >= n || path.size() == k) {
            if (sum == n && path.size() == k) {
                res.push_back(path);
            }
            return;
        }
        for (int i = startIdx; i <= 9; ++i) {
            if (n - i + 1 < k - path.size()) {
                continue;
            }
            sum += i;
            path.push_back(i);
            backtracking(k, n, i + 1, sum);
            path.pop_back();
            sum -= i;
        }
    }
};

void test216()
{
    Solution2 solve = Solution2();
    vector<vector<int>> nums = solve.combinationSum3(3, 9);
    for (auto &num : nums) {
        print(num);
    }
}

class Solution3
{
  public:
    // 17. 对每个数字枚举 多个数字进行组合
    unordered_map<char, string> mp = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}};
    vector<string> res;
    string path;
    vector<string> letterCombinations(string digits)
    {
        // 仅包含2-9的字符串
        // map={2:"abc", 3:"def", 4:"ghi", 5:"jkl", 6:"mno", 7:"pqrs", 8:"tuv",9:"wxyz"};
        path.clear();
        res.clear();
        backtracking(digits, 0);
        return res;
    }

    void backtracking(string &digits, int index)
    {
        if (index == digits.size()) {
            res.emplace_back(path);
            return;
        }
        char key = digits[index];
        string letters = mp[key];
        // digits[idx]才是回溯时的变量
        // i是用来遍历letters的
        for (int i = 0; i < letters.size(); ++i) {
            path.push_back(letters[i]);
            backtracking(digits, index + 1);
            path.pop_back();
        }
    }
};

void test17()
{
    Solution3 solve = Solution3();
    print(solve.letterCombinations("23"));
    print(solve.letterCombinations(""));
    print(solve.letterCombinations("2"));
}

class Solution4
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        path.clear();
        res.clear();
        backtracking(candidates, target, 0, 0);
        return res;
    }

    void backtracking(vector<int> &candidates, int target, int startIdx, int sum)
    {
        if (sum >= target) {
            if (sum == target) {
                res.push_back(path);
            }
            return;
        }
        for (int i = startIdx; i < candidates.size(); ++i) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, i, sum);
            path.pop_back();
            sum -= candidates[i];
        }
    }
};

void test39()
{
    Solution4 solve = Solution4();
    vector<int> candidates1 = {2, 3, 6, 7};
    vector<int> candidates2 = {2, 3, 5};
    int target1 = 7;
    int target2 = 8;
    vector<vector<int>> nums1 = solve.combinationSum(candidates1, target1);
    vector<vector<int>> nums2 = solve.combinationSum(candidates2, target2);
    for (auto &num : nums1) {
        print(num);
    }
    for (auto &num : nums2) {
        print(num);
    }
}

class Solution5
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        path.clear();
        res.clear();
        std::sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return res;
    }

    void backtracking(vector<int> &candidates, int target, int startIdx, int sum)
    {
        if (sum >= target) {
            if (sum == target) {
                res.push_back(path);
            }
            return;
        }
        for (int i = startIdx; i < candidates.size(); ++i) {
            if (i > startIdx && candidates[i] == candidates[i - 1]) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, i + 1, sum);
            path.pop_back();
            sum -= candidates[i];
        }
    }
};

void test40()
{
    Solution5 solve = Solution5();
    vector<int> candidates1 = {10, 1, 2, 7, 6, 1, 5};
    vector<int> candidates2 = {2, 5, 2, 1, 2};
    int target1 = 8;
    int target2 = 5;
    vector<vector<int>> nums1 = solve.combinationSum2(candidates1, target1);
    vector<vector<int>> nums2 = solve.combinationSum2(candidates2, target2);
    for (auto &num : nums1) {
        print(num);
    }
    for (auto &num : nums2) {
        print(num);
    }
}

class Solution6
{
  public:
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<string>> partition(string s)
    {
        path.clear();
        res.clear();
        backtracking(s, 0);
        return res;
    }
    // 双指针判断回文
    bool isPalindrome(string &s)
    {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s[i++] != s[j--]) {
                return false;
            }
        }
        return true;
    }
    // startIdx 切分位置
    void backtracking(string &s, int startIdx)
    {
        // 出口：切割到头了
        if (startIdx == s.length()) {
            res.emplace_back(path);
            return;
        }
        for (int i = startIdx; i < s.length(); ++i) {
            string sub = s.substr(startIdx, i - startIdx + 1);
            if (!isPalindrome(sub)) { // 不是回文不用回溯了，直接下一步
                continue;
            }
            path.emplace_back(sub);
            backtracking(s, i + 1);
            path.pop_back();
        }
    }
};

void test131()
{
    Solution6 solve = Solution6();
    string s = "aab";
    auto nums = solve.partition(s);
    for (auto &num : nums) {
        print(num);
    }
}

class Solution7
{
  public:
    vector<string> res;
    string path;
    vector<string> restoreIpAddresses(string s)
    {
        backtracking(s, 0, 0);
        return res;
    }
    // 各部分是否合法 0-255
    bool isValid(string &s)
    {
        if (s.length() > 3) { // 四位数必大于255
            return false;
        }
        if (s.empty()) {
            return false;
        }
        // 含前导0不合法，单0合法
        // 大于255不合法
        if (s.length() != 1 && s.front() == '0' || stoi(s) > 255) {
            return false;
        }
        return true;
    }

    void backtracking(string &s, int startIdx, int pointNum)
    {
        if (pointNum == 3) {
            // 检查第四段
            string lastStr = s.substr(startIdx);
            if (isValid(lastStr)) {
                auto lastBegin = path.end();
                path.append(lastStr);
                res.emplace_back(path);
                path.erase(lastBegin, path.end());
            }
            return;
        }
        for (int i = startIdx; i < s.length(); ++i) {
            string sub = s.substr(startIdx, i - startIdx + 1);
            if (!isValid(sub)) {
                continue;
            }
            auto lastBegin = path.end(); // 记录上次的尾迭代器
            sub.push_back('.');
            path.append(sub);
            ++pointNum;
            backtracking(s, i + 1, pointNum);
            --pointNum;
            path.erase(lastBegin, path.end());
        }
    }
};

void test93()
{
    Solution7 solve = Solution7();
    // string s = "25525511135";
    string s = "010010";
    auto res = solve.restoreIpAddresses(s);
    print(res);
}

class Solution8
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsets(vector<int> &nums)
    {
        backtracking(nums, 0);
        return res;
    }

    void backtracking(vector<int> &nums, int startIdx)
    {
        // 递归终止可以不写，循环跑到nums.size()自然停止
        res.emplace_back(path);
        for (int i = startIdx; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
};

class Solution8_2
{
  public:
    vector<vector<int>> subsets(vector<int> &nums)
    {
        vector<vector<int>> res;
        res.push_back({}); // 加上空集
        for (int i = 0; i < nums.size(); ++i) {
            int length = res.size();
            for (int j = 0; j < length; ++j) {
                vector<int> path = res[j];
                path.push_back(nums[i]);
                res.emplace_back(path);
            }
        }
        return res;
    }
};

void test78()
{
    Solution8 solve = Solution8();
    Solution8_2 solve2 = Solution8_2();
    vector<int> nums = {1, 2, 3};
    auto res = solve.subsets(nums);
    auto res2 = solve2.subsets(nums);
    for (auto &r : res) {
        print(r);
    }
    for (auto &r : res2) {
        print(r);
    }
}

class Solution9
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int> &nums)
    {
        std::sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return res;
    }

  private:
    void backtracking(vector<int> &nums, int startIdx)
    {
        // 递归终止可以不写，循环跑到nums.size()自然停止
        res.emplace_back(path);
        for (int i = startIdx; i < nums.size(); ++i) {
            if (i > startIdx && nums[i] == nums[i - 1]) {
                continue;
            }
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
};

void test90()
{
    Solution9 solve = Solution9();
    vector<int> nums = {2, 2, 2};
    auto res = solve.subsetsWithDup(nums);
    for (auto &r : res) {
        print(r);
    }
}

class Solution10
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> findSubsequences(vector<int> &nums)
    {
        res.clear();
        path.clear();
        backtracking(nums, 0);
        return res;
    }

    void backtracking(vector<int> &nums, int startIdx)
    {
        if (path.size() > 1) {
            res.push_back(path);
        }
        // 因无法排序，不能通过紧挨着的数字去重
        // 只能利用nums范围{-100,100}，哈希到used上去重
        vector<bool> used(201, false);
        for (int i = startIdx; i < nums.size(); ++i) {
            if (used[nums[i] + 100]){
                continue;
            }
            if (!path.empty() && nums[i] < path.back()){
                continue;
            }
            used[nums[i] + 100] = true; // 回溯函数内的无需“回溯”
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
};

void test491()
{
    Solution10 solve = Solution10();
    vector<int> nums1 = {4, 6, 7, 7};
    vector<int> nums2 = {4, 4, 3, 2, 1};
    auto res = solve.findSubsequences(nums1);
    for (auto &r : res) {
        print(r);
    }
    res = solve.findSubsequences(nums2);
    cout << "--------" << endl;
    for (auto &r : res) {
        print(r);
    }
}

class Solution11
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return res;
    }

    void backtracking(vector<int> &nums, vector<bool> &used)
    {
        if (path.size() == nums.size()) {
            res.emplace_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }
};

void test46()
{
    Solution11 solve = Solution11();
    vector<int> nums = {1, 2, 3}; // 无重复
    auto res = solve.permute(nums);
    for (auto &r : res) {
        print(r);
    }
}

class Solution12
{
  public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        vector<bool> used(nums.size(), false);
        std::sort(nums.begin(), nums.end());
        backtracking(nums, used);
        return res;
    }

    void backtracking(vector<int> &nums, vector<bool> &used)
    {
        if (path.size() == nums.size()) {
            res.emplace_back(path);
            return;
        }
        // 横向控制for循环，纵向控制递归
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) {
                continue;
            }
            // used[i-1]=False 同一层上    过滤掉相同元素
            // used[i-1]=True  同一树枝上  不过滤相同元素
            // 其实加上used[i-1]==false是为了让同一树枝上相同元素，不被continue掉
            // 而同一层的相同元素是==true的，会被continue掉
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }
};

void test47()
{
    Solution12 solve = Solution12();
    vector<int> nums = {1, 1, 2}; // 有重复
    auto res = solve.permuteUnique(nums);
    for (auto &r : res) {
        print(r);
    }
}

class Solution13
{
  public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n)
    {
        vector<string> chessboard(n, string(n, '.')); // 建棋盘
        backtracking(chessboard, 0, n);
        return res;
    }

    bool isValid(vector<string> &chessboard, int row, int col, int n)
    {
        // 剪枝
        // 行不用检查，行由回溯决定每行只放一个
        // 检查列，只需检查到当前行row
        for (int i = 0; i < row; ++i) {
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查左上，即135度
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查右上，即45度
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    void backtracking(vector<string> &chessboard, int row, int n)
    {
        if (row == n) {
            res.emplace_back(chessboard);
            return;
        }
        for (int col = 0; col < n; ++col) { // dim=1方向-->
            if (!isValid(chessboard, row, col, n)) {
                continue;
            }
            chessboard[row][col] = 'Q';
            // 放下一行，所以isvalid无需考虑行
            backtracking(chessboard, row + 1, n); // dim=0方向 向下
            chessboard[row][col] = '.';
        }
    }
};

class Solution14
{
  public:
    void solveSudoku(vector<vector<char>> &board)
    {
        // 9*9 棋盘
        backtracking(board);
    }

    bool isValid(vector<vector<char>> &board, int row, int col, char val)
    {
        for (int j = 0; j < 9; ++j) {
            if (board[row][j] == val) {
                return false;
            }
        }
        for (int i = 0; i < 9; ++i) {
            if (board[i][col] == val) {
                return false;
            }
        }
        int innerRow = row / 3 * 3;
        int innerCol = col / 3 * 3;
        for (int i = innerRow; i < innerRow + 3; ++i) {
            for (int j = innerCol; j < innerCol + 3; ++j) {
                if (board[i][j] == val) {
                    return false;
                }
            }
        }
        return true;
    }

    bool backtracking(vector<vector<char>> &board)
    {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                // 空格才需要填
                if (board[i][j] != '.') {
                    continue;
                }
                // 尝试放置1-9
                // 采坑：不能写num<'10'，这个字符不和1-9连续
                for (char num = '1'; num <= '9'; ++num) {
                    if (!isValid(board, i, j, num)) {
                        continue;
                    }
                    board[i][j] = num;
                    // 找到一个可能的数立即返回
                    if (backtracking(board)) {
                        return true;
                    }
                    board[i][j] = '.';
                }
                // 1-9都尝试完了
                return false;
            }
        }
        return true;
    }
};

int main()
{
    // test77();
    // test216();
    // test17();
    // test39();
    // test40();
    // test131();
    // test93();
    // test78();
    // test90();
    // test46();
    // test47();
    test491();
    return 0;
}